package ACwing.P3SearchandGraph.BFS;

import java.io.*;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Date : 2023-04-02
 * @Description:AcWing 844. 走迷宫
 */
public class Maze {
    static int n,m;
    static Map<Integer,Integer> map=new HashMap();
    static int N=110;
    static int [][] g=new int[N][N];  //存储图
    static int [][] d=new int[N][N];  //每个点到起点的距离
    static List<PII> q=new ArrayList(); //存储路径
    static BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw= new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        String[] strings = br.readLine().split("\\s+");
        n=Integer.parseInt(strings[0]);
        m=Integer.parseInt(strings[1]);
        String[] nums;
        //读入图
        for (int i = 0; i < n; i++) {
            nums = br.readLine().split("\\s+");
            for (int j = 0; j < m; j++) {
                g[i][j]=Integer.parseInt(nums[j]);
            }
        }
        //初始化 距离
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                d[i][j]=-1;
            }
        }
        d[0][0]=0;//起点

        System.out.println(bfs());
    }
    static int bfs(){
        int hh=0,tt=0;//模拟队列
        q.add(0, new PII(0, 0));
        //用加上向量来表示往上下左右前进  依次上右下左  -1,0  0,1  1,0  0,-1
        int []dx={-1,0,1,0},dy={0,1,0,-1};
        while(hh<=tt){
            PII t=q.get(hh++);

            //比较四个方向
            for (int i = 0; i < 4; i++) {
                int x=t.x+dx[i],y=t.y+dy[i];
                //在边界内 0 m n，并且 可以走  （g是0）  且没有走过(d是-1)
                if(x>=0  &&  x<n  && y>=0 && y<m && g[x][y]==0 &&d[x][y]==-1){
                    d[x][y]=d[t.x][t.y]+1;//第 xy 个点 是第几层
                    q.add(++tt, new PII(x, y)); //加入路径
                }
            }


        }
        //返回右下角的点
        return d[n-1][m-1];
    }

    static class PII {
        int x;
        int y;
        public PII(int x,int y){
            this.x=x;
            this.y=y;
        }
    }

}
